package com.kehao.leetcode.hard.tree_graph;

import com.kehao.utils.LeetCodeUtil;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class FindOrderSolution {
    int[] visit;
    List<Integer>[] listArray;
    Stack<Integer> stack;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        stack = new Stack<>();
        visit = new int[numCourses];
        listArray= new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            listArray[i] = new ArrayList<>();
        }
        for(int[] num:prerequisites){
            listArray[num[1]].add(num[0]);
        }
        for (int i = 0; i < numCourses; i++) {
            if(visit[i]==0) {
                if(dfs(i)==false) return new int[0];
            }
        }
        int[] result = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            result[i]=stack.pop();
        }
        return result;
    }

    private boolean dfs(int i){
        if(visit[i]==1) return false;
        if(visit[i]==2) return true;
        visit[i] = 1;
        for(int j : listArray[i]){
            if(dfs(j)==false) return false;
        }
        visit[i] = 2;
        stack.add(i);
        return true;
    }

    @Test
    public void test(){
        String s = LeetCodeUtil.bracketTransform("[[1,0],[2,0],[3,1],[3,2]]");
        System.out.println(s);
    }

    @Test
    public void test01(){
        int numCourses = 4;
        int[][] prerequisites = {{1,0},{2,0},{3,1},{3,2}};
        Arrays.stream(findOrder(numCourses, prerequisites)).forEach(i-> System.out.println(i+" "));
    }

}
